#include"contextfree.h"

using std::istream;
using std::ostream;
using std::vector;
using std::set;
using std::map;
using std::multimap;
using std::endl;
using std::string;
using std::pair;
using std::swap;
using std::make_pair;

NameStorage CFGrammar::initNames() {
	NameStorage res;
	res.addName("");
	return res;
}

NameStorage CFGrammar::names = CFGrammar::initNames();

string CFGrammar::resolve(int i) {
	if (i >= 0) {
		return names[i];
	} else {
		string temp;
		temp . push_back((char)(-i));
		return temp;
	}
}

string CFGrammar::resolve(vector<int> const & vi) {
	string res;
	for( vector<int>::const_iterator it = vi . begin(); it != vi . end(); ++it )
		res += resolve(*it);
	return res;
}

string CFGrammar::resolve(vector<int> const & vi, vector<int>::const_iterator vit) {
	string res;
	for( ; vit != vi . end(); ++vit )
		res += resolve(*vit);
	return res;
}

bool CFGrammar::CNFRule(vector<int> const & ci) {
	return (ci . size() == 1 && ci[0] < 0) ||
		(ci . size() == 2 && ci[0] > 0 && ci[1] > 0);
}

bool CFGrammar::CNFChainRule(vector<int> const & ci) {
	return ci . size() == 1 ||
		(ci . size() == 2 && ci[0] > 0 && ci[1] > 0);
}

string CFGrammar::extractAlNum(string const & str) {
	string res;
	for(unsigned i = 0; i < str.length(); i++)
		if (isalnum(str[i]))
			res.push_back(str[i]);
	return res;
}

vector<int> CFGrammar::unresolve(string const & s) {
	vector<int> res;
	string temp;
	for( string::const_iterator it = s . begin(); it != s . end(); ++it ) {
		if (isupper(*it)) {
			temp = "";
			temp . push_back(*it);
			res . push_back((int)names . addName(temp));
		} else {
			if (isalnum(*it))
				res . push_back((int)(- *it));
		}
	}
	return res;
}

pair<unsigned, vector<int> > CFGrammar::getRuleFromStream(istream & in) {
	string r;
	getline(in, r);
	size_t pos = r . find_first_of(':');
	if (pos == string :: npos)
		return make_pair((unsigned)0, vector<int>());
	else {
		string temp = r . substr(0, pos);
		unsigned first = names . addName(extractAlNum(temp));
		vector<int> second = unresolve(r . substr(pos + 1, string::npos));
		return make_pair(first, second);
	}
}

CFGrammar::CFGrammar() : starting(0), clean(true), chainCNF(true), CNF(true) {}

CFGrammar::CFGrammar(CFGrammar const & cfg) : starting(cfg . starting), rules(cfg . rules),
			clean(cfg . clean), chainCNF(cfg . chainCNF), CNF(cfg . CNF) {}
			
CFGrammar::~CFGrammar() {}

ostream & operator<<(ostream & out, CFGrammar const & cfg) {
	out << CFGrammar::names[cfg . starting] << endl;
	for( multimap<unsigned, vector<int> >::const_iterator it = cfg . rules . begin();
						it != cfg . rules . end(); ++it ) {
		out << CFGrammar::names[it -> first] << " : " << CFGrammar::resolve(it -> second) << endl;
	}
	return out;
}

istream & operator>>(istream & in, CFGrammar & cfg) {
	cfg . rules = multimap<unsigned, vector<int> >();
	cfg . clean = false;
	cfg . chainCNF = true;
	cfg . CNF = true;
	string temp;
	getline(in, temp);
	cfg . starting = CFGrammar::names . addName(CFGrammar::extractAlNum(temp));
	pair<unsigned, vector<int> > p;
	while (in . good()) {
		p = CFGrammar::getRuleFromStream(in);
		if (p . first != 0) {
			cfg . rules . insert(p);
			if (!CFGrammar::CNFRule(p . second)) {
				cfg . CNF = false;
				if (!CFGrammar::CNFChainRule(p . second))
					cfg . chainCNF = false;
			}
		}
	}
	return in;
}

CFGrammar CFGrammar::cleanedup() const {
	CFGrammar cfg(*this);
	cfg . cleanup();
	return cfg;	
}

CFGrammar CFGrammar::chainNormalized() const {
	CFGrammar cfg(*this);
	cfg . chainNormalize();
	return cfg;	
}

CFGrammar CFGrammar::normalized() const {
	CFGrammar cfg(*this);
	cfg . normalize();
	return cfg;	
}

void CFGrammar::cleanup() {
	if (!clean) {
		set<unsigned> good;
		good . insert(starting);
		size_t prevSize = 0, nextSize = 1;
		set<unsigned> nextGood;
		while( nextSize > prevSize ) {
			nextGood = good;
			for( set<unsigned>::const_iterator it = good . begin(); it != good . end(); ++it ) {
				multimap<unsigned, vector<int> >::const_iterator lower = rules . lower_bound(*it);
				multimap<unsigned, vector<int> >::const_iterator upper = rules . upper_bound(*it);
				for( ; lower != upper; ++lower ) {
					for( vector<int>::const_iterator itv = lower -> second . begin();
								itv != lower -> second . end(); ++itv ) {
						if (*itv > 0)
							nextGood . insert(*itv);
					}
				}
			}
			swap(nextGood, good);
			swap(prevSize, nextSize);
			nextSize = good . size();
		}
		for( multimap<unsigned, vector<int> >::iterator itm = rules . begin();
						itm != rules . end(); ) {
			if (good . find(itm -> first) == good . end() || itm -> second . size() == 0)
				rules . erase(itm++);
			else
				++itm;
		}
		clean = true;
	}
}

void CFGrammar::chainNormalize() {
	cleanup();
	if (!chainCNF) {
		map<char, unsigned> termSubst;
		for( multimap<unsigned, vector<int> >::iterator itm = rules . begin();
				itm != rules . end(); ++itm ) {
			if (itm -> second . size() > 1) {
				for( vector<int>::iterator itv = itm -> second . begin();
						itv != itm -> second . end(); ++itv ) {
					if (*itv < 0) {
						char c = (char)(- *itv);
						map<char, unsigned>::const_iterator itf =
								termSubst . find(c);
						if (itf != termSubst . end()) {
							*itv = itf -> second;
						} else {
							string temp;
							temp = "/";
							temp . push_back(c);
							unsigned newState = names . addOrRename(temp);
							termSubst[c] = newState;
							*itv = newState;
						}
					}
				}
			}
		}
		for( map<char, unsigned>::const_iterator it = termSubst . begin(); it != termSubst . end(); ++it ) {
			vector<int> temp2;
			temp2 . push_back(- it -> first);
			rules . insert(make_pair(it -> second, temp2));
		}				
	}
	multimap<unsigned, vector<int> > newRules;
	for( multimap<unsigned, vector<int> >::const_iterator it = rules . begin();
			it != rules . end(); ++it ) {
		if (!CNFChainRule(it -> second)) {
			unsigned prevState, nextState;
			vector<int> temp;
			prevState = it -> first;
			for( vector<int>::const_iterator itv = it -> second . begin();
					itv + 2 != it -> second . end(); ++itv ) {
				nextState = names . addOrRename("(" + resolve(it -> second, itv + 1) + ")");
				temp = vector<int>();
				temp . push_back(*itv);
				temp . push_back((int)nextState);
				newRules . insert(make_pair(prevState, temp));
				swap(prevState, nextState);
			}
			temp = vector<int>();
			temp . push_back(it -> second[it -> second . size() - 2]);
			temp . push_back(it -> second[it -> second . size() - 1]);
			newRules . insert(make_pair(prevState, temp));
		} else {
			newRules . insert(*it);
		}
	}
	rules = newRules;
	chainCNF = true;
}

template <typename T, typename S>
bool existsInMultimap(multimap<T, S> const & m,
		pair<T, S> const & p) {
	typename multimap<T, S>::const_iterator lower = m . lower_bound(p . first);
	typename multimap<T, S>::const_iterator upper = m . upper_bound(p . first);
	bool stop = false;
	for( ; !stop && lower != upper; ++lower)
		stop = lower -> second == p . second;
	return stop;
}
template <typename T, typename S>
void addIfNotExists(multimap<T, S> & m,
		pair<T, S> const & p) {
	if (!existsInMultimap(m, p))
		m . insert(p);
}

multimap<unsigned, unsigned> CFGrammar::transClosure(multimap<unsigned, unsigned> m) {
	multimap<unsigned, unsigned> res;
	size_t prevSize = 0, nextSize = m . size();
	while (nextSize > prevSize) {
		for( multimap<unsigned, unsigned>::const_iterator it = m . begin();
				it != m . end(); ++it ) {
			addIfNotExists(res, (pair<unsigned, unsigned> const)*it);
			multimap<unsigned, unsigned>::const_iterator lower = m . lower_bound(it -> second);
			multimap<unsigned, unsigned>::const_iterator upper = m . upper_bound(it -> second);
			pair<unsigned, unsigned> p;
			p . first = it -> first;
			for( ; lower != upper; ++lower ) {
				p . second = lower -> second;
				addIfNotExists(res, p);
			}
		}
		swap(prevSize, nextSize);
		nextSize = res . size();
		m = res;
	}
	return res;
}

set<vector<int> > mutateRulePos(set<vector<int> > r,
		multimap<unsigned, unsigned> const & sub, size_t pos) {
	set<vector<int> > res;
	for( set<vector<int> >::const_iterator it = r . begin();
			it != r . end(); ++it ) {
		multimap<unsigned, unsigned>::const_iterator lower = sub . lower_bound((*it)[pos]);
		multimap<unsigned, unsigned>::const_iterator upper = sub . upper_bound((*it)[pos]);
		vector<int> temp;
		temp = *it;
		for( ; lower != upper; ++lower ) {
			temp[pos] = (int)lower -> second;
			res . insert(temp);
		}
	}
	return res;
}

set<vector<int> > CFGrammar::mutateRule(vector<int> const & r,
		multimap<unsigned, unsigned> const & sub) {
	set<vector<int> > res, temp;
	res . insert(r);
	for( size_t pos = 0; pos < r . size(); ++pos )
		res = mutateRulePos(res, sub, pos);
	return res;
}
	 

void CFGrammar::normalize() {
	cleanup();
	chainNormalize();
	if (!CNF) {
		multimap<unsigned, unsigned> subst;
		for( multimap<unsigned, vector<int> >::const_iterator it = rules . begin();
				it != rules . end(); ++it ) {
			addIfNotExists(subst, make_pair(it -> first, it -> first));
			if (it -> second . size() == 1 && it -> second[0] > 0)
				addIfNotExists(subst, make_pair(it -> first, (unsigned)it -> second[0]));
		}
		subst = transClosure(subst);
		for( multimap<unsigned, vector<int> >::iterator it = rules . begin();
				it != rules . end(); ) {
			if( it -> second . size() == 1 && it -> second[0] > 0 )
				rules . erase(it++);
			else
				++it;
		}
		multimap<unsigned, vector<int> > newRules;
		set<vector<int> > temp;
		for( multimap<unsigned, vector<int> >::const_iterator it = rules . begin();
				it != rules . end(); ++it ) {
			if( it -> second . size() == 1)
				addIfNotExists(newRules, (pair<unsigned, vector<int> > const)*it);
			else {
				temp = mutateRule(it -> second, subst);
				for( set<vector<int> >::const_iterator its = temp . begin();
						its != temp . end(); ++its )
					addIfNotExists(newRules, make_pair(it -> first, *its));
			}
		}
		rules = newRules;
		CNF = true;						
	}
}

size_t translate(size_t i, size_t j, size_t N) {
	if (i > j) swap(i, j);
	return i*N + j;
}

bool CFGrammar::CYK(string const & s) const {
	if (!clean || !chainCNF || !CNF) return normalized() . CYK(s);
	size_t N = s . length();
	set<unsigned> * dynamic = new set<unsigned>[N * N];
	for( size_t i = 0; i < N ; ++i) {
		for( multimap<unsigned, vector<int> >::const_iterator it = rules . begin();
				it != rules . end(); ++it ) {
			if (it -> second[0] == (int)-s[i])
				dynamic[translate(i, i, N)] . insert(it -> first);
		}
	}
	size_t j;
	for( size_t d = 1; d < N; ++d ) {
		for( size_t i = d; i < N ; ++i ) {
			j = i - d;
			// [j,k] (k,i]
			for( size_t k = j; k < i; ++k ) {
				for( multimap<unsigned, vector<int> >::const_iterator it = rules . begin();
						it != rules . end(); ++it ) {
					if (it -> second . size() == 2 &&
							dynamic[translate(j, k, N)] . find(it -> second[0]) !=
							dynamic[translate(j, k, N)] . end() &&
							dynamic[translate(k + 1, i, N)] . find(it -> second[1]) !=
							dynamic[translate(k + 1, i, N)] . end())
						dynamic[translate(i, j, N)] . insert(it -> first);
				}
			}
		}
	}
	return dynamic[translate(0, N - 1, N)] . find(starting) != dynamic[translate(0, N - 1, N)] . end();
	delete[] dynamic;
}
